package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.LinkedProblem;

import java.util.HashMap;

/**
 * https://leetcode.com/problems/copy-list-with-random-pointer/
 * 最呆写法
 * <p>
 * TODO 还有一种把 oldNode1 -> newNode1 -> oldNode2 -> newNode2的神奇做法
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC138 implements LinkedProblem {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        if (head == null) return null;
        HashMap<Integer, Node[]> map = new HashMap<>();
        HashMap<Node, Integer> map1 = new HashMap<>();
        int i = 0;
        Node cur = head;
        while (cur != null) {
            map.put(i, new Node[]{new Node(cur.val), cur});
            map1.put(cur, i);
            cur = cur.next;
            i++;
        }
        for (Integer index : map.keySet()) {
            Node[] nodes = map.get(index);

            if (nodes[1].next != null) {
                nodes[0].next = map.get(index + 1)[0];
            }
            if (nodes[1].random != null) {
                nodes[0].random = map.get(map1.get(nodes[1].random))[0];
            }
        }
        return map.get(0)[0];
    }

    public static void main(String[] args) {
        System.out.println(new LC138());
    }
}
